1. Field of the Invention
The present invention relates to a method, apparatus, and computer readable storage for implementing a recursive hierarchical segmentation algorithm on parallel computers. More particularly, the present invention enables a computer system to utilize parallel processes to perform the hierarchical segmentation algorithm, therein decreasing computation time and enabling the creation of hierarchical segmentations on large data sets that would be impracticable just using serial processing.
2. Description of the Related Art
Image segmentation is a partitioning of an image into sections or regions. These regions may be later associated with ground cover type or land use, but the segmentation process simply gives generic labels (i.e. region 1, region 2, etc. . . . ) to each region. The regions consist of groups of multispectral or hyperspectral image pixels that have similar data feature values. These data feature values may be the multispectral or hyperspectral data values themselves and/or they may be derivative features such as band ratios or textural features.
FIG. 1 illustrates a satellite image of the Baltimore, Md. region. FIG. 2 illustrates the image of FIG. 1 after undergoing segmentation into two region sets. As can be seen by FIG. 2, like regions have been joined. The darker colored region corresponds to bodies of water, while the lighter colored region represents the land. FIG. 3 illustrates the image of FIG. 1 after undergoing segmentation into three region sets. As can be seen by FIG. 3, the image is colored into three image sets, each image set containing a like region. The dark colored region corresponds to land, the medium colored region corresponds to water, and the light colored regions correspond to the industrial or dense urban regions.
As can be seen by the FIGS. 1-3, the hierarchical image segmentations can be useful in a multitude of applications, including earth science applications where delineation of the spatial coverage of water or land is required. It can also be used as substitute ground reference data for the validation of the analysis of lower resolution global coverage remotely sensed data.
There are numerous algorithms for achieving image segmentation, including recursive algorithms. However, most of these algorithms do not employ any form of optimization in performing segmentations. The following is the classic definition of image segmentation:                Let X be a two-dimensional array representing an image. A segmentation of X can be defined as a partition of X into disjoint subsets X1, X2, . . . , XN, such that             1      )        ⁢                   ⁢                  ⋃                  i          =          1                    N        ⁢          X      i        =  X        2) Xi, i=1, 2, . . . , N is connected.        3) P(Xi)=TRUE for i=1, 2, . . . , N and        4) P(Xi∪Xj)=FALSE for i≠j, where Xi and Xj are adjacent.        P(Xi) is a logical predicate that assigns the value TRUE or FALSE to Xi, depending on the image data values in Xi.S. W. Zucker, “Region growing: childhood and adolescence,” Computer Graphics and Image Processing, Vol. 5, pp. 382-399, 1976, summarized the above definition as follows: The first condition requires that every picture element (pixel) must be in a region. The second condition requires that each region must be connected, i.e. composed of contiguous image pixels. The third condition determines what kind of properties each region must satisfy, i.e. what properties the image pixels must satisfy to be considered similar enough to be in the same region. The fourth condition specifies that, in the final segmentation result, any merging of any adjacent regions would violate the third condition.        
A problem with this classic definition of image segmentation is that the segmentation so defined is not unique. The number, N and shape of the partitions, Xi, X2, . . . , XN, depend on the order in which the image pixels are processed. In addition, there is no concept of optimality contained in this definition of image segmentation. Under this classic definition, all partitions that satisfy the conditions represent equally good or valid segmentations of the image.
An ideal definition of image segmentation would be as follows:                Let X be a two-dimensional array representing an image. A segmentation of X into N regions can be defined as a partition of X into disjoint subsets X1, X2, . . . , XN, such that             1      )        ⁢                   ⁢                  ⋃                  i          =          1                    N        ⁢          X      i        =  X        2) Xi, i=1, 2, . . . , N is connected.             3      )        ⁢                   ⁢                  ∑                  i          =          1                N            ⁢              G        ⁢                  (                      X            i                    )                      =  MINIMUM         over all partitions into N regions and        4) G(Xi∪Xj)>G(Xi)+G(Xj) for i≠j, where Xi and Xj are adjacent.        G(Xi) is a function that assigns a cost to partition Xi, depending on the image data values in Xi.        
These conditions can be summarized as follows: The first condition requires that every picture element (pixel) must be in one of N regions. The second condition requires that each region must be connected, i.e. composed of contiguous image pixels. The third condition states that the partition must produce a minimum cost aggregated over all N regions. The fourth condition specifies that, in the final segmentation result, any merging of adjacent regions increases the minimum cost obtained in the third condition.
As a result of these conditions, the order dependence problem is eliminated because the global minimum solution is found and this solution is the optimal solution. In practice, this ideal image segmentation is difficult, if not impossible, to find. The third condition implies that all possible image partitions consisting of N regions must be searched to find the minimum cost. Further, the question of the proper value for N is left undetermined.
B. J. Schachter, L. S. Davis and A. Rosenfeld, “Some experiments in image segmentation by clustering of local feature vectors,” Pattern Recognition, Vol. 11, No. 1, pp. 19-28, 1979, suggest that an iterative parallel region growing process be used to eliminate the order dependence problem. R. L. Kettig and D. A. Landgrebe, “Computer classification of remotely sensed multispectral image data by extraction and classification of homogeneous objects,” LARS Information Note 050975, Laboratory for Applications of Remote Sensing, Purdue University, West Lafayette, Ind., 1975, suggest an alternative partitioning logic in which the most similar neighboring region is merged first, but found this approach too difficult to implement in a sequential manner with the computing resources they had at that time. J. C. Tilton and S. C. Cox, “Segmentation of remotely sensed data using parallel region growing,” Digest of the 1983 International Geoscience and Remote Sensing Symposium, San Francisco, Calif., pp. 9.1-9.6, Aug. 31-Sep. 2, 1983, propose implementing an iterative parallel approach to region growing on parallel processors in order to overcome the computational demands of this approach. In their approach, the most similar pair(s) of spatially adjacent regions is (are) merged at each iteration. This approach solved the order dependence problem (assuming a deterministic tie-breaking method is employed), but did not fully address the optimal segmentation problem. Merging the most similar pair(s) of spatially adjacent regions at each iteration does not guarantee that the segmentation result at a particular iteration is the optimal partition of the image data for the number of partitions obtained at that iteration. J.-M. Beaulieu and M. Goldberg, “Hierarchy in picture segmentation: A stepwise optimization approach,” IEEE Trans. on Pattern Analysis and Machine Intelligence, Vol. 11, No. 2, pp. 150-163, February 1989, provide a theoretical basis for Tilton and Cox's iterative parallel region growing approach in their theoretical analysis of their similar Hierarchical Stepwise Optimization algorithm (HSWO). They show that the HSWO algorithm produces the globally optimal segmentation result if each iteration is statistically independent. Even though each iteration will generally not be statistically independent for natural images, the HSWO approach is shown to still produce excellent results. Beaulieu and Goldberg also point out that the sequence of partitions generated by this iterative approach reflect the hierarchical structure of the imagery data: the partitions obtained in the early iterations preserve the small details and objects in the image, while the partitions obtained in the latter iterations preserve only the most important components of the image. They further note that these hierarchical partitions may carry information that may help in identifying the objects in the imagery data.
The definition of image segmentation as followed by the HSWO algorithm is defined recursively as follows:                Let X be a two-dimensional array representing an image and let Xi, X2, . . . , XN−1, XN be a partition of X into N regions such that             1      )        ⁢                   ⁢                  ⋃                  i          =          1                    N        ⁢          X      i        =      X    ⁢                   ⁢    and          2) Xi, i=1, 2, . . . , N is connected.        Let G(Xi) be a function that assigns a cost to partition Xi, depending on the image data values in Xi. Reorder the partition Xi, X2, . . . , XN−1, XN such that G(XN−1∪XN)≦G(Xi∪Xj) for all i≠j where XN−1 and XN are adjacent and Xi and Xj, are adjacent. The segmentation of X into N−1 regions is defined as the partition X′1, X′2. . . , X′N−1 where X′i=Xi for i=1, 2, . . . , N−2 and X′N−1=XN−1∪XN.The initial partition may assign each image pixel to a separate region, in which case the initial value of N is the number of pixels in the image (Np). Any other initial partition may be used, such as a partitioning of the image into n×n blocks, where n2<<Np, or any pre-segmentation with another algorithm.        
The region growing approach utilized by the hierarchical image segmentation algorithm, HSEG, is the same as that employed by Beaulieu and Goldberg's HSWO algorithm except that HSEG may optionally alternate spectral clustering iterations with region growing iterations to merge non-adjacent regions. Such spectral clustering adds robustness to the segmentation result and eliminates the bookkeeping overhead of separately accounting for essentially identical non-adjacent regions.
A problem with implementing segmentation algorithms based on HSWO region growing is that these algorithms are processor intensive. A large high-resolution high-bit image can take a very long time to undergo segmentation using the prior art HSWO region growing algorithms and related technology.
An additional problem common to all recursive segmentation algorithms is the requirement of large amounts of memory, making it likely that large images may require more memory than available, preventing large images from being segmented.